/**
 * 
 */
package com.module.hq.engine;

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;

import com.dalonedrau.graph.DijkstraComparator;
import com.dalonedrau.graph.DijkstraSearch;
import com.dalonedrau.graph.Graph;
import com.dalonedrau.graph.GraphEdge;
import com.dalonedrau.graph.TwoDMapGraphNode;
import com.dalonedrau.graph.WeightedGraphEdge;
import com.dalonedrau.jogl.engine.Interactive;
import com.dalonedrau.jogl.engine.JOGLErrorHandler;
import com.dalonedrau.jogl.util.UtilityMethods;
import com.module.hq.bus.flyweights.HQTerrainTypes;
import com.module.hq.bus.globals.HQGlobals;
import com.module.hq.bus.globals.SpellConsts;
import com.module.hq.graph.HQCellGraph;

/**
 * @author Donald
 */
public class HQDijkstraSearch implements DijkstraSearch {
	/** the singleton instance of {@link HQDijkstraSearch}. */
	private static HQDijkstraSearch	instance;
	/**
	 * Gets the singleton instance of {@link HQDijkstraSearch}.
	 * @return {@link HQDijkstraSearch}
	 */
	public static HQDijkstraSearch getInstance() {
		if (HQDijkstraSearch.instance == null) {
			HQDijkstraSearch.instance = new HQDijkstraSearch();
		}
		return HQDijkstraSearch.instance;
	}
	/** the node comparator. */
	private DijkstraComparator	comparator;
	/**
	 * this is indexed into by node index and holds the total cost of the best
	 * path found so far to the given node. For example, costToThisNode[5] will
	 * hold the total cost of all the edges that comprise the best path to node
	 * 5 found so far in the search (if node 5 is present and has been visited
	 * of course).
	 */
	private float[]				costToThisNode;
	/** the graph being searched. */
	private HQCellGraph			graph;
	/** the reference id of the current source IO. */
	private int					ioid;
	/** the list of predecessor nodes. */
	private int[]				listOfPredecessors;
	/** the maximum distance the IO can travel in a search. */
	private int					maxDistance;
	/** the number of settled nodes. */
	private int					numSettled;
	/** the list of settled nodes, by index. */
	private int[]				settled;
	/** the source node from where the search originates. */
	private int					source;
	/** the list of unsettled nodes, by index. */
	private ArrayList<Integer>	unsettled;
	/** Hidden constructor. */
	private HQDijkstraSearch() {}
	/**
	 * Adds a node index to the list of settled nodes.
	 * @param val the node index
	 */
	private void addToSettled(final int val) {
		if (numSettled + 1 >= settled.length) {
			int[] dest = new int[settled.length + 1];
			System.arraycopy(settled, 0, dest, 0, settled.length);
			settled = dest;
			dest = null;
		}
		settled[numSettled] = val;
		numSettled++;
	}
	/**
	 * Adds a node to the list of unsettled nodes.
	 * @param val the node id
	 */
	private void addToUnsettled(final int val) {
		unsettled.add(val);
		Collections.sort(unsettled, comparator);
	}
	/**
	 * Determines if the IO can traverse a specific node. PCs can enter any open
	 * node that doesn't have a hostile NPC, while NPCs can enter any open node
	 * that doesn't have a PC (and the NPC isn't hostile). Any PC or NPC can
	 * walk through walls with the spell PASS THROUGH ROCK enabled.
	 * @param nodeId the node id
	 * @return true if the IO can cross the node; false otherwise
	 */
	private boolean canIOTraverseCell(final int nodeId) {
		boolean can = true;
		try {
			HQInteractiveObject io =
					(HQInteractiveObject) Interactive.getInstance().getIO(ioid);
			TwoDMapGraphNode node = graph.getNode(nodeId);
			int x = node.getLocation().x;
			int y = node.getLocation().y;
			int cellType = HQMap.getInstance().getCellType(x, y);
			int floor = HQTerrainTypes.getInstance().getTerrainId(
					"ultima_floor_to_wall");
			int open = HQTerrainTypes.getInstance().getTerrainId(
					"ultima_door_open_to_floor");
			int wall = HQTerrainTypes.getInstance().getTerrainId(
					"ultima_wall_to_floor");
			int closed = HQTerrainTypes.getInstance().getTerrainId(
					"ultima_door_closed_to_floor");
			int secret = HQTerrainTypes.getInstance().getTerrainId(
					"ultima_secret_door_closed_to_floor");
			if (cellType == floor
					|| cellType == open) {
				// the IO can always walk through open spaces
				// see if there is a hostile IO there
				if (io.hasIOFlag(HQGlobals.IO_01_PC)) {
					// check cell for hostile NPC's
					int ioid2 =
							HQMap.getInstance().getActiveIOsAtLocation(x, y);
					if (ioid2 > -1) {
						HQInteractiveObject io2 =
								(HQInteractiveObject) Interactive.getInstance()
										.getIO(ioid2);
						if (io2 == null) {
							throw new Exception("Invalid IO identifier " 
									+ ioid2 + " referenced at map cell " + x 
									+ "," + y);
						}
						if (io2.hasIOFlag(HQGlobals.IO_03_NPC)
								&& HQScript.getInstance().hasLocalVariable(
										ioid2, "enemy")) {
							int enemyVal =
									HQScript.getInstance()
											.getLocalLongVariableValue(
													ioid2, "enemy");
							if (enemyVal == 1) {
								can = false;
							}
						}
					}
				} else if (io.hasIOFlag(HQGlobals.IO_03_NPC)) {
					// check cell for hostile PC's
					int ioid2 =
							HQMap.getInstance().getActiveIOsAtLocation(x, y);
					if (ioid2 > -1) {
						HQInteractiveObject io2 =
								(HQInteractiveObject) Interactive.getInstance()
										.getIO(
												ioid2);
						if (io2.hasIOFlag(HQGlobals.IO_01_PC)
								&& HQScript.getInstance().hasLocalVariable(
										ioid, "enemy")) {
							int enemyVal =
									HQScript.getInstance()
											.getLocalLongVariableValue(
													ioid, "enemy");
							if (enemyVal == 1) {
								can = false;
							}
						}
					}
				}
			} else if (cellType == wall
					|| cellType == secret) {
				// IO can walk through walls and secret doors with spell on
				if (!HQSpells.getInstance().hasSpellOn(
						ioid, SpellConsts.SPELL_09_EARTH_PASS_THROUGH_ROCK)) {
					can = false;
				}
			} else {
				// don't move through closed doors. make player open them
				can = false;
			}
		} catch (Exception ex) {
			JOGLErrorHandler.getInstance().fatalError(ex);
		}
		return can;
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public float[] getDistances() {
		return costToThisNode;
	}
	public float getDistanceTo(final Point target) throws Exception {
		int val = graph.getNode(target.x, target.y).getIndex();
		float cost = Float.POSITIVE_INFINITY;
		if (costToThisNode[val] > -1) {
			cost = costToThisNode[val];
		}
		return cost;
	}
	private float getDistanceTo(final int val) {
		float cost = Float.POSITIVE_INFINITY;
		if (costToThisNode[val] > -1) {
			cost = costToThisNode[val];
		}
		return cost;
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public int getNumPredecessors() {
		return listOfPredecessors.length;
	}
	public int[] getPathToTarget(final Point target) throws Exception {
		int[] path = getPathToTarget(
				graph.getNode(target.x, target.y).getIndex());
		// convert nodes to locations
		for (int i = 0; i < path.length; i++) {
			Point pt = graph.getNode(path[i]).getLocation();
			path[i] = UtilityMethods.getInstance().convertPointToInt(pt);
			pt = null;
		}
		return path;
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public int[] getPathToTarget(final int target) {
		int[] path = new int[] { target };
		int lastNode = HQDijkstraSearch.getInstance().getPredecessor(target);
		while (lastNode != -1) {
			int[] dest = new int[path.length + 1];
			System.arraycopy(path, 0, dest, 0, path.length);
			dest[path.length] = lastNode;
			path = dest;
			dest = null;
			lastNode =
					HQDijkstraSearch.getInstance().getPredecessor(lastNode);
		}
		// reverse the path
		int[] dest = new int[path.length];
		int m = path.length - 1;
		for (int i = 0; i <= m; i++) {
			dest[m - i] = path[i];
		}
		path = dest;
		dest = null;
		return path;
	}
	public int getPredecessor(final int index) {
		return listOfPredecessors[index];
	}
	/**
	 * Pops a value off the list of settled nodes.
	 * @return <code>int</code>
	 */
	private int popOffSettled() {
		int val = settled[0];
		for (int i = 1; i < settled.length; i++) {
			settled[i - 1] = settled[i];
		}
		settled[settled.length - 1] = -1;
		numSettled--;
		return val;
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public void search(final int src) throws Exception {
		if (graph == null) {
			throw new Exception("No Graph was set.");
		}
		source = src;
		comparator = new DijkstraComparator(this);
		// add source to list of unsettled vertices and immediately sort
		addToUnsettled(source);
		costToThisNode[source] = 0;
		// while the list of unsettled vertices still has nodes
		while (!unsettled.isEmpty()) {
			// get the node with the current shortest distance
			int nextClosestNode = unsettled.remove(0);
			// add next closest node to list of settled vertices
			addToSettled(nextClosestNode);
			// settled.add(nextClosestNode);
			// relax the neighbors of next closest node. For each edge connected
			// to the next closest node
			GraphEdge[] edges = graph.getEdgesFromNode(nextClosestNode);
			for (int i = 0; i < edges.length; i++) {
				int v = edges[i].getTo();
				// check to see if the edge goes to a node the IO can traverse
				if (!canIOTraverseCell(v)) {
					continue;
				}
				float distToV = getDistanceTo(v);
				float distToU = getDistanceTo(nextClosestNode);
				WeightedGraphEdge edge = (WeightedGraphEdge) edges[i];
				if (distToV > maxDistance
						&& distToU + edge.getCost() > maxDistance) {
					// skip node that is too far away
					continue;
				}
				if (!settledContains(v)) {
					if (distToV > distToU + edge.getCost()) {
						costToThisNode[v] = (float) (distToU + edge.getCost());
						listOfPredecessors[v] = nextClosestNode;
						addToUnsettled(v);
					}
				}
			}
		}
	}
	/**
	 * Searches for all paths from an IO's location.
	 * @param id the reference id of the source IO
	 * @throws Exception if an error occurs
	 */
	public void searchByIO(final int id) throws Exception {
		ioid = id;
		int node = HQMap.getInstance().getGraphNodeIndexForIO(ioid);
		// is the IO under the spell SWIFT WIND
		HQInteractiveObject io =
				(HQInteractiveObject) Interactive.getInstance().getIO(ioid);
		if (io.hasIOFlag(HQGlobals.IO_01_PC)) {
			HQPlayer.getInstance().computePlayerFullStats(io);
			maxDistance = 
				io.getScript().getLocalVariable("movesLeft").getIntVal();
		}
		search(node);
	}
	/**
	 * {@inheritDoc}
	 */
	@Override
	public void setGraph(final Graph g) {
		graph = (HQCellGraph) g;
		source = -1;
		numSettled = 0;
		if (costToThisNode == null) {
			costToThisNode = new float[graph.getNumberOfNodes()];
		} else {
			if (costToThisNode.length < graph.getNumberOfNodes()) {
				float[] dest = new float[graph.getNumberOfNodes()];
				System.arraycopy(
						costToThisNode, 0, dest, 0, costToThisNode.length);
				costToThisNode = dest;
				dest = null;
			}
		}
		for (int i = 0; i < costToThisNode.length; i++) {
			costToThisNode[i] = -1;
		}
		settled = new int[graph.getNumberOfNodes()];
		unsettled = new ArrayList<Integer>(graph.getNumberOfNodes());
		listOfPredecessors = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < listOfPredecessors.length; i++) {
			listOfPredecessors[i] = -1;
		}
	}
	/**
	 * Determines if the settled array contains a specific index.
	 * @param val the index
	 * @return true if the settled array contains a specific index; false
	 *         otherwise
	 */
	private boolean settledContains(final int val) {
		boolean found = false;
		for (int i = 1; i < settled.length; i++) {
			if (settled[i] == val) {
				found = true;
				break;
			}
		}
		return found;
	}

}
